# -*- coding: utf-8 -*-
from structures.hashtable import HashTable


class UnionFind():

    def __init__(self, items):
        self.sets = HashTable()
        for item in items:
            node = [item, None, 1]
            self.sets[item] = node
        self.__count = len(items)

    def find(self, item):
        node = self.sets[item]
        while node[1] is not None:
            node = node[1]
        return node[0]

    def union(self, item1, item2):
        if item1 != item2:
            node1 = self.sets[item1]
            node2 = self.sets[item2]

            if node1[2] < node2[2]:
                node1[1] = node2
                node2[2] += node1[2]
            else:
                node2[1] = node1
                node1[2] += node2[2]
            self.__count -= 1

    def count(self):
        return self.__count


#class UnionFindNode():
#
#    def __init__(self, item):
#        self.item = item
#        self.set = None
#        self.size = 1
